package problem;

import java.util.LinkedList;
import java.util.Queue;

public class S_117 {

class Node {
    public int val;
    public Node left;
    public Node right;
    public Node next;

    public Node() {}

    public Node(int _val,Node _left,Node _right,Node _next) {
        val = _val;
        left = _left;
        right = _right;
        next = _next;
    }
}

    //1.递归
    class Solution {
        public Node connect(Node root) {
            //自顶向下递归
            if(root==null) return null;

            //1.构建当前节点的左节点
            if(root.left!=null){
                //1.1有右节点就连上
                if(root.right!=null) root.left.next=root.right;
                //1.2没有右节点就找到父节点的兄弟节点的最左节点
                else root.left.next=findLeftChild(root);
            }

            //2.构建当前节点的右节点
            if(root.right!=null)
                root.right.next=findLeftChild(root);

            //递归

            connect(root.left);
            connect(root.right);

            return root;
        }
        //查找当前节点的最左边兄弟节点的左孩子
        private Node findLeftChild(Node root){
            if(root.next==null) return null;
            while (root.next!=null){
                if(root.next.left!=null) return root.next.left;
                if(root.next.right!=null) return root.next.right;
                root=root.next;
            }
            return null;
        }
    }

    //2.队列BFS，利用pre
    class Solution1{
        public Node connect(Node root){
            if(root==null) return null;
            Queue<Node> queue=new LinkedList<>();
            queue.offer(root);
            while(!queue.isEmpty()){
                int size=queue.size();
                Node pre=null;
                for(int i=0;i<size;i++){
                    Node cur=queue.poll();
                    if(i>0) pre.next=cur;
                    pre=cur;
                    if(cur.left!=null) queue.offer(root.left);
                    if(cur.right!=null) queue.offer(root.right);
                }
            }
            return root;
        }
    }
}
